package org.liaohailong.helloworld.practice;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Author: liaohailong
 * Time: 2021/6/22 10:39
 * Describe: 初级算法 - 数学
 */
public class MathPractice {

    // LC Fizz Buzz
//    public List<String> fizzBuzz(int n) {
//        LinkedList<String> result = new LinkedList<>();
//        for (int i = 1; i <= n; i++) {
//            boolean times3 = isTimes(i, 3);
//            boolean times5 = isTimes(i, 5);
//            StringBuilder sb = new StringBuilder();
//            if (!times3 && !times5) {
//                sb.append(i);
//            } else {
//                if (times3)
//                    sb.append("Fizz");
//                if (times5)
//                    sb.append("Buzz");
//            }
//            result.add(sb.toString());
//
//        }
//        return result;
//    }

//    private boolean isTimes(int i, int t) {
//        String s = String.valueOf(i * 1f / t);
//        if (s.contains(".")) {
//            String[] split = s.split("\\.");
//            String res = split[split.length - 1].replaceAll("0", "");
//            return res.length() < 1;
//        } else return true;
//    }


    // LC Fizz Buzz
    public List<String> fizzBuzz(int n) {
        LinkedList<String> result = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 15 == 0) {
                result.add("FizzBuzz");
            } else if (i % 5 == 0) {
                result.add("Buzz");
            } else if (i % 3 == 0) {
                result.add("Fizz");
            } else result.add(String.valueOf(i));
        }
        return result;
    }

    // LC 计数质数
    public int countPrimes(int n) {
        int sqrt = (int) Math.sqrt(n);
        // 先把所有合数都找出来
        boolean[] dp = new boolean[n + 1];
        for (int i = 2; i <= sqrt; i++) {
            if (dp[i]) continue;
            for (int j = i * i; j < n; j += i) {
                dp[j] = true;
            }
        }

        int total = 0;
        for (int i = 2; i < n; i++) {
            if (!dp[i]) total++;
        }

        return total;
    }

    // LC 3的幂
    public boolean isPowerOfThree(int n) {
//        if (n == 1) return true;
//        if (n % 3 != 0) return false;
//
//        int x = 3;
//        int t = 1;
//        int y = 3;
//        while (true) {
//            if (y == n) return true;
//            else if (n < y) return false;
//            t++;
//            y = (int) Math.pow(x, t);
//        }

        if (n > 1)
            while (n % 3 == 0)
                n /= 3;
        return n == 1;
    }

    // LC 罗马数字转整数
    public int romanToInt(String s) {
        char[] chars = s.toCharArray();
        int total = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            int currVal = getValue(chars[i]);

            int value = currVal;
            int prev = i - 1;
            if (prev >= 0) {
                int prevVal = getValue(chars[prev]);
                if (prevVal < currVal) {
                    value -= prevVal;
                    i--;
                }
            }

            total += value;
        }

        return total;
    }

    private int getValue(char ch) {
        switch (ch) {
            case 'I':
                return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
            default:
                return 0;
        }
    }

}
